package offerbook;

/**
 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。

 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

 方式1：列举
 n = 1,则 1;

 n = 2.则1,1横  1,1竖；是不是有点眼熟；

 n= 3,则1,1,1横 ，1,1横1竖， 1竖1,1横，
 f(n) = f(n-1) + f(n-2)

 方式2：假设大矩形就是2*8，方法数记为f(8)
 用第一个1*2的小矩形覆盖大矩形的最左边有两种选择，横或竖。
 当竖着放，大的还剩2*7是f(7)；
 当横着放，左上角放一个1*2的，下方再放一个1*2，那么大的还剩2*6=f(6).
 所以f(8) = f(7) + f(6)

 */
public class Code09_FillRectangle {

    public int methodNum(int n){
        if(n == 1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        return methodNum(n-1)+methodNum(n-2);
    }
}
